/*
 * Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.util;

import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;
import sun.misc.SharedSecrets;

/**
 * 基于hash table的<tt>Map</tt>接口实现. 该实现提供了所有可选的map操作, 并允许
 * <tt>null</tt> values和<tt>null</tt> key. (<tt>HashMap</tt>类大致相当于
 * <tt>Hashtable</tt>, 除了它是unsynchronized的并且允许null值). 这个类不保证
 * map的顺序; 特别是它不能保证, 它不能保证顺序随时间的推移保持不变.
 *
 * <p>该实现为基本操作(<tt>get</tt>和<tt>put</tt>)提供恒定的时间性能, 假设hash函数
 * 将元素适当地分散到桶中. Iteration collection views所需的时间与<tt>HashMap</tt>
 * 实例的"capacity"(桶的数量)加上它的大小(key-value映射的数量)成正比. 因此, 如果迭代
 * 性能很重要, 就不要将初始容量设置得太高(或负载因子设置得太低).
 *
 * <p><tt>HashMap</tt>的实例有两个影响其性能的参数: <i>initial capacity</i>和
 * <i>load factor</i>. <i>capacity</i>是hash table中的桶数, 初始容量只是hash
 * table创建时的容量. <i>load factor</i>是在hash table自动增加之前允许达到的满度
 * 的度量. 当hash table中的条目数超过负载因子和当前容量的乘积时, hash table将
 * <i>rehashed</i>(即重建内部数据结构), 这样hash table的桶数约为原来的两倍.
 *
 * <p>作为一般规则, 默认负载因子(.75)在时间和空间成本之间提供了很好的权衡. 较高的值
 * 会减少空间开销, 但会增加查找成本(反映在<tt>HashMap</tt>类的大多数操作中, 包括
 * <tt>get</tt>和<tt>put</tt>). 在设置map的初始容量时, 应考虑map中期望的条目数
 * 及其负载因子, 以减少rehash操作的次数. 如果初始容量大于最大条目数除以负载因子, 则
 * 不会发生rehash操作.
 *
 * <p>如果要将许多映射存储在<tt>HashMap</tt>实例中, 那么用足够大的容量创建它将比
 * 让它根据需要执行自动rehash来扩展table更有效地存储映射. 注意, 使用相同{@code hashCode()}
 * 的多个key肯定会降低任何hash table的性能. 为了改善影响, 当key为{@link Comparable}
 * 时, 这个类可以使用key之间的comparison顺序来帮助打破束缚.
 *
 * <p><strong>注意, 这个实现不是同步的.</strong> 如果多个线程并发访问一个hash map,
 * 并且至少有一个线程在结构上修改了map, 那么它<i>必须</i>在外部同步. (结构修改是添加或
 * 删除一个或多个额映射的任何操作; 仅仅改变与实例中已经包含的key相关联的value并不是结构
 * 修改.) 这通常是通过在自然封装映射的某些对象上同步来实现的.
 *
 * 如果不存在这样的对象, 则应该使用{@link Collections#synchronizedMap Collections.synchronizedMap}
 * "包装"映射. 这最好在创建时完成, 以防止对map的意外不同步访问:<pre>
 *   Map m = Collections.synchronizedMap(new HashMap(...));</pre>
 *
 * <p>这个类的所有"collection view methods"返回的iterator都是<i>fail-fast</i>:
 * 如果map在iterator创建后的任何时间被结构修改, 除了通过iterator自己的remove方法外,
 * iterator将抛出{@link ConcurrentModificationException}. 因此, 在面对并发修改时,
 * iterator会快速而干净地失败, 而不是在未来不确定的时间发生任意的、不确定的行为.
 *
 * <p>注意, iterator的快速失败行为不能得到保证, 因为一般来说, 在存在不同步的并发修改时,
 * 不可能做出任何硬保证. 快速失败iterator尽可能抛出<tt>ConcurrentModificationException</tt>.
 * 因此, 编写一个依赖于此异常的程序是错误的: <i>iterator的快速失败行为应该只用于检查错误.</i>
 *
 * <p>这个类是
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework的成员</a>.
 *
 * @param <K> 此map维护的key的类型
 * @param <V> 映射值的类型
 *
 * @author  Doug Lea
 * @author  Josh Bloch
 * @author  Arthur van Hoff
 * @author  Neal Gafter
 * @see     Object#hashCode()
 * @see     Collection
 * @see     Map
 * @see     TreeMap
 * @see     Hashtable
 * @since   1.2
 */
public class HashMap<K,V> extends AbstractMap<K,V>
		implements Map<K,V>, Cloneable, Serializable {

	private static final long serialVersionUID = 362498820763181265L;

	/*
	 * 实现注意事项.
	 *
	 * 这个map通常充当一个分bin(桶), 但是当容器太大时, 它们被转换为TreeNodes的容器,
	 * 每个容器的结构类似于java.util.TreeMap中的容器. 大多数方法尝试使用普通的bin,
	 * 但在适用的情况下中继到TreeNode方法(简单地通过检查节点的实例). TreeNodes的容器
	 * 可以像其他容器一样被遍历和使用, 但是在过度填充时还支持更快的查找. 然而, 由于正常
	 * 使用的绝大多数容器都没有过度填充, 所以在table方法的过程中可能会延迟检查树容器的
	 * 存在.
	 *
	 * Tree bins(即元素都是TreeNodes的容器)主要由hashCode排序, 但在ties的情况下,
	 * 如果两个元素属于相同的"class C implements Comparable<C>", 则使用他们的
	 * compareTo方法进行排序. (我们通过反射保守地检查泛型类型来验证这一点 -- 参见方法
	 * comparableClassFor). 当key具有不同的hash或可排序时, tree  bin增加的复杂性
	 * 对于提供最坏情况下的O(log n)操作是值得的. 因此, 在hashCode()方法返回分布不佳
	 * 的值, 以及许多key共享一个hashCode的值(只要它们也是可比较的)的偶然或恶意使用下,
	 * 性能会优雅的下降. 如果这两种方法都不适用, 与不猜与预防措施相比, 我们可能会浪费大约
	 * 两倍的时间和空间. 但已知的唯一情况源于糟糕的用户编程实践, 这些实践依据非常缓慢,
	 * 因此影响甚微.)
	 *
	 * 因为TreeNodes大约是常规节点的两倍大, 所以我们只在容器包含足够的节点以保证使用时
	 * 才使用它们(参见TREEIFY_THRESHOLD). 当它们变得太小(由于删除或调整大小), 它们
	 * 会被转换回普通的容器. 在分别良好的用户hashCode的用法中, 很少使用tree bin.
	 * 理想情况下, 在随机hashCode下, bin中的节点频率遵循泊松分布
	 * (http://en.wikipedia.org/wiki/Poisson_distribution), 对于默认的调整
	 * 大小阈值0.75, 该分布的参数平均约0.5, 尽管由于调整大小粒度的差异很大. 忽略方差,
	 * list大小k的期望出现次数为 (exp(-0.5) * pow(0.5, k) / factorial(k)).
	 * 第一个值是:
	 *
	 * 0:    0.60653066
	 * 1:    0.30326533
	 * 2:    0.07581633
	 * 3:    0.01263606
	 * 4:    0.00157952
	 * 5:    0.00015795
	 * 6:    0.00001316
	 * 7:    0.00000094
	 * 8:    0.00000006
	 * 更多: 少于千万分之一
	 *
	 * 树的根通常是它的第一个节点. 然而, 有时(目前仅针对Iterator.remove), 根可能
	 * 在其他地方, 但可以在父links(方法TreeNode.root())后恢复.
	 *
	 * 所有适用的内部方法都接受hash code作为参数(通常由公共方法提供), 允许他们相互
	 * 调用而无需重新计算用户hashCode. 大多数内部方法也接受"tab"参数, 通常是当前表,
	 * 但是在调整大小或转换时可能是新的或旧的.
	 *
	 * 当bin list被树化、分割或未分割时, 我们将它保持相同的相对访问/遍历顺序(即字段
	 * Node.next), 以更好地保持局部性, 并稍微简化调用iterator.remove的分割和遍历
	 * 处理. 在插入时使用comparator, 为了在重平衡过程中保持总顺序(或尽可能接近此处
	 * 所要求的顺序), 我们将类和identityHashCodes进行比较.
	 *
	 * 由于子类LinkedHashMap的存在, 普通模式和树模式之间的使用和转换变得复杂起来.
	 * 请参见下文, 了解定义为在插入、删除和访问时调用的钩子方法, 这些方法允许LinkedHashMap
	 * 内部以其他方式独立于这些机制. (这还要求将map实例传递给一些困难创建新节点的实用
	 * 程序方法.)
	 *
	 * 基于SSA的并行编程风格有助于避免所有扭曲的指针操作中出现混叠错误.
	 */

	/**
	 * 默认的初始容量-必须是2的幂.
	 */
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 又名16

	/**
	 * 最大容量, 如果更高的值由任何一个构造函数用参数隐式指定, 则使用该值.
	 * 必须是2的幂<= 1<<30.
	 */
	static final int MAXIMUM_CAPACITY = 1 << 30;

	/**
	 * 在构造函数中没有指定时使用的负载因子.
	 */
	static final float DEFAULT_LOAD_FACTOR = 0.75f;

	/**
	 * 对于bin使用树而不是list时的bin计数阈值. 当向至少有这么多节点的bin中添加
	 * 元素时, bin将转换为树. 该值必须大于2, 并且应该至少为8, 以便与树移除中关于
	 * 收缩时转换回普通bin的假设相匹配.
	 */
	static final int TREEIFY_THRESHOLD = 8;

	/**
	 * 在调整大小操作期间取消树化(分割)bin的bin计数阈值. 应小于TREEIFY_THRESHOLD,
	 * 最多为6, 以便在移除时进行收缩检测.
	 */
	static final int UNTREEIFY_THRESHOLD = 6;

	/**
	 * 可以多容器进行树化的最小table容量. (否则, 如果一个bin中有太多的节点,
	 * 则会调整table的大小). 应该至少是4 * TREEIFY_THRESHOLD, 以避免调整
	 * 大小和树化阈值之间的冲突.
	 */
	static final int MIN_TREEIFY_CAPACITY = 64;

	/**
	 * 基本的hash bin节点, 用于大多数条目.
	 * (参见下面的TreeNode子类, 以及LinkedHashMap的Entry子类.)
	 */
	static class Node<K,V> implements Map.Entry<K,V> {
		// 该节点中存放的key的hash值(经过HashMap计算的)
		final int hash;
		// 该节点中存放的key
		final K key;
		// 该节点中存放的value
		V value;
		// 链表中的下一个节点的引用
		Node<K,V> next;

		Node(int hash, K key, V value, Node<K,V> next) {
			this.hash = hash;
			this.key = key;
			this.value = value;
			this.next = next;
		}

		public final K getKey()        { return key; }
		public final V getValue()      { return value; }
		// toString同时输出key和value, 他们都很重要
		public final String toString() { return key + "=" + value; }

		// 使用^操作可以使得key和value的改变都可以影响到计算结果.
		// 使用其他的计算方式无论是&还是|都有可能导致key、value的hashCode变了但是计算结果不变
		public final int hashCode() {
			return Objects.hashCode(key) ^ Objects.hashCode(value);
		}

		// setValue时将返回旧值
		public final V setValue(V newValue) {
			V oldValue = value;
			value = newValue;
			return oldValue;
		}

		public final boolean equals(Object o) {
			if (o == this)
				return true;
			if (o instanceof Map.Entry) {
				Map.Entry<?,?> e = (Map.Entry<?,?>)o;
				if (Objects.equals(key, e.getKey()) &&
						Objects.equals(value, e.getValue()))
					return true;
			}
			return false;
		}
	}

	/* ---------------- Static utilities -------------- */

	/**
	 * 计算key.hashCode()并将较高的hash位(XORs)扩散到较低的hash位. 因为表使用
	 * 2的次方掩码, 所以仅在当前掩码以上的位变化的hash set总是会碰撞. (已知的例子
	 * 是在小表中保存联系整数的Float key集). 所以我们应用一个变换, 向下传播更高位
	 * 的影响. bit传播速度的、效用和质量之间需要权衡. 因为许多常见的hash set已经被
	 * 合理地分布(因此不能从扩散中受益), 而且因为我们使用tree来处理bin中的大量冲突,
	 * 所以我们只需以最便宜的方式对一些以为的bit进行异或, 以减少系统损失, 并合并最高
	 * bit的影响, 否则由于 表边界, 这些bit将永远不会用于索引计算.
	 */
	static final int hash(Object key) {
		int h;
		return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
	}

	/**
	 * 如果想的Class的形式为"class C implements Comparable<C>", 则返回
	 * x的class, 否贼为null.
	 */
	static Class<?> comparableClassFor(Object x) {
		if (x instanceof Comparable) {
			Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
			if ((c = x.getClass()) == String.class) // bypass checks
				return c;
			if ((ts = c.getGenericInterfaces()) != null) {
				for (int i = 0; i < ts.length; ++i) {
					if (((t = ts[i]) instanceof ParameterizedType) &&
							((p = (ParameterizedType)t).getRawType() ==
									Comparable.class) &&
							(as = p.getActualTypeArguments()) != null &&
							as.length == 1 && as[0] == c) // type arg is c
						return c;
				}
			}
		}
		return null;
	}

	/**
	 * Returns k.compareTo(x) if x matches kc (k's screened comparable
	 * class), else 0.
	 */
	@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
	static int compareComparables(Class<?> kc, Object k, Object x) {
		return (x == null || x.getClass() != kc ? 0 :
				((Comparable)k).compareTo(x));
	}

	/**
	 * 返回一个大于等于给定容量的2的幂值.
	 */
	static final int tableSizeFor(int cap) {
		int n = cap - 1;
		n |= n >>> 1;
		n |= n >>> 2;
		n |= n >>> 4;
		n |= n >>> 8;
		n |= n >>> 16;
		return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
	}

	/* ---------------- Fields -------------- */

	/**
	 * 该table在首次使用时初始化, 并根据需要调整大小. 分配时, 长度总是2的幂.
	 * (在某些操作中, 我们还允许长度为0, 以允许当前不需要的自举机制.)
	 */
	transient Node<K,V>[] table;

	/**
	 * 保存缓存的entrySet(). 请注意, AbstractMap字段用于keySet()和values().
	 */
	transient Set<Map.Entry<K,V>> entrySet;

	/**
	 * 此map中包含的key-vale映射的数量.
	 */
	transient int size;

	/**
	 * 结构修改是只改变HashMap中映射数量或以其他方式修改其内部结构(例如, rehash)的修改.
	 * 该字段用于使HashMap Collection-views上的iterator快速失败.
	 * (见ConcurrentModificationException).
	 */
	transient int modCount;

	/**
	 * 要调整大小的下一个大小值(容量*负载因子).
	 *
	 * @serial
	 */
	// (在序列化时, javadoc描述为true.
	// 此外, 如果表数据没有被分配, 这个字段将保留初始数组容量, 或者0表示
	// DEFAULT_INITIAL_CAPACITY.)
	int threshold;

	/**
	 * hash table的负载因子.
	 *
	 * @serial
	 */
	final float loadFactor;

	/* ---------------- Public operations -------------- */

	/**
	 * 使用指定的初始容量和负载因子构造一个空的<tt>HashMap</tt>.
	 *
	 * @param  initialCapacity 初始容量
	 * @param  loadFactor      负载因子
	 * @throws IllegalArgumentException 如果初始容量为负或负载系数为非正
	 */
	public HashMap(int initialCapacity, float loadFactor) {
		if (initialCapacity < 0)
			throw new IllegalArgumentException("Illegal initial capacity: " +
					initialCapacity);
		if (initialCapacity > MAXIMUM_CAPACITY)
			initialCapacity = MAXIMUM_CAPACITY;
		if (loadFactor <= 0 || Float.isNaN(loadFactor))
			throw new IllegalArgumentException("Illegal load factor: " +
					loadFactor);
		this.loadFactor = loadFactor;
		this.threshold = tableSizeFor(initialCapacity);
	}

	/**
	 * 使用指定的初始容量和默认负载因子(0.75)构造一个空的<tt>HashMap</tt>.
	 *
	 * @param  initialCapacity 初始容量.
	 * @throws IllegalArgumentException 如果初始容量为负.
	 */
	public HashMap(int initialCapacity) {
		this(initialCapacity, DEFAULT_LOAD_FACTOR);
	}

	/**
	 * 使用默认初始容量(16)和默认负载因子(0.75)构造一个空的<tt>HashMap</tt>.
	 */
	public HashMap() {
		this.loadFactor = DEFAULT_LOAD_FACTOR; // 所有其他字段默认
	}

	/**
	 * 使用与指定的<tt>Map</tt>相同的映射构造新的<tt>HashMap</tt>.
	 * <tt>HashMap</tt>是以默认负载因子(0.75)和足以容纳指定<tt>Map</tt>中的映射的
	 * 初始容量创建的.
	 *
	 * @param   m 要将其映射放置在此map中的map
	 * @throws  NullPointerException 如果指定的map为null
	 */
	public HashMap(Map<? extends K, ? extends V> m) {
		this.loadFactor = DEFAULT_LOAD_FACTOR;
		putMapEntries(m, false);
	}

	/**
	 * 实现Map.putAll和Map构造函数
	 *
	 * @param m the map
	 * @param evict 最初构造此map时为false, 否则为true
	 * (传递给afterNodeInsertion方法).
	 */
	final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
		int s = m.size();
		// 只有在指定map有原始的情况下才处理, 没有的话肯定就不用处理了
		if (s > 0) {
			// 如果本HashMap原来没有存放数组, 那就需要计算一下数组长度了
			// 首先根据指定map的大小计算长度, 如果计算出来的长度比初始化的时候大, 那就进行一次调整
			if (table == null) { // pre-size
				float ft = ((float)s / loadFactor) + 1.0F;
				int t = ((ft < (float)MAXIMUM_CAPACITY) ?
						(int)ft : MAXIMUM_CAPACITY);
				if (t > threshold)
					threshold = tableSizeFor(t);
			}
			// 如果本HashMap已经存放过元素了, 且指定Map的大小超过了本Map的当前容量值, 则进行resize
			else if (s > threshold)
				resize();
			// 遍历指定的map, 将其元素一个一个的放入我们的map中
			for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
				K key = e.getKey();
				V value = e.getValue();
				putVal(hash(key), key, value, false, evict);
			}
		}
	}

	/**
	 * 返回此map中的key-value映射的数量.
	 *
	 * @return 此map中的key-value映射的数量
	 */
	public int size() {
		return size;
	}

	/**
	 * 如果此map中不包含key-value映射, 则返回<tt>true</tt>.
	 *
	 * @return 如果此map不包含key-value映射, 则为<tt>true</tt>
	 */
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * 返回指定key映射到的value, 如果该map不包含key的映射, 则返回{@code null}.
	 *
	 * <p>更正式地说, 如果这个map包含一个从key{@code k}到value{@code v}的映射,
	 * 使得{@code (key==null ? k==null : key.equals(k))}, 那么这个方法返回
	 * {@code v}; 否则它返回{@code null}. (最多只能有一个这样的映射.)
	 *
	 * <p>{@code null}的返回值不<i>一定</i>表示map不包含key的映射; 也有可能map
	 * 显式地将key映射到{@code null}. {@link #containsKey containsKey}运算
	 * 可以用来区分这两种情况.
	 *
	 * @see #put(Object, Object)
	 */
	public V get(Object key) {
		Node<K,V> e;
		return (e = getNode(hash(key), key)) == null ? null : e.value;
	}

	/**
	 * 实现了Map.get和相关方法
	 *
	 * @param hash key的hash
	 * @param key the key
	 * @return node, 如果没有则为null
	 */
	final Node<K,V> getNode(int hash, Object key) {
		Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
		// 如果table存在且该hash值映射到的table元素处, 第一个节点不为null, 则可以开始处理
		if ((tab = table) != null && (n = tab.length) > 0 &&
				(first = tab[(n - 1) & hash]) != null) {
			if (first.hash == hash && // 总是检查第一个节点
					((k = first.key) == key || (key != null && key.equals(k))))
				return first;
			// 如果第一个节点不满足条件, 且存在后续节点
			if ((e = first.next) != null) {
				// 如果第一个节点是树节点, 则调用树节点的查找方法
				if (first instanceof TreeNode)
					return ((TreeNode<K,V>)first).getTreeNode(hash, key);
				// 如果是链表, 则循环处理链表接待您, 调用key的equals方法判断是否相等
				do {
					if (e.hash == hash &&
							((k = e.key) == key || (key != null && key.equals(k))))
						return e;
				} while ((e = e.next) != null);
			}
		}
		return null;
	}

	/**
	 * 如果此map中包含指定key的映射, 则返回<tt>true</tt>.
	 *
	 * @param   key   要测试其在该map中的存在的key
	 * @return <tt>true</tt>, 如果此map包含指定的映射
	 * key.
	 */
	public boolean containsKey(Object key) {
		return getNode(hash(key), key) != null;
	}

	/**
	 * 将指定value与此map中的指定key关联. 如果先前的map包含key的映射, 则替换旧值.
	 *
	 * @param key 要与指定value相关联的key
	 * @param value 要与指定key关联的value
	 * @return 与<tt>key</tt>关联的前一个值, 如果<tt>key</tt>没有映射, 则为
	 *         tt>null</tt>. (<tt>null</tt>返回还可以指示map先前将
	 *         <tt>null</tt>与<tt>key</tt>关联.)
	 */
	public V put(K key, V value) {
		return putVal(hash(key), key, value, false, true);
	}

	/**
	 * 实现Map.put和相关方法
	 *
	 * @param hash key的hash
	 * @param key the key
	 * @param value 要put的value
	 * @param onlyIfAbsent 如果为true, 则不要更改现有值
	 * @param evict 如果为false, 则table处于创建模式.
	 * @return 以前的值, 如果没有则为null
	 */
	final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
	               boolean evict) {
		Node<K,V>[] tab; Node<K,V> p; int n, i;
		// 如果table为null或者长度为0, 则resize, 并记录数组长度
		if ((tab = table) == null || (n = tab.length) == 0)
			n = (tab = resize()).length;
		// 判断该hash映射的索引位置是否有元素, 没有则创建一个
		if ((p = tab[i = (n - 1) & hash]) == null)
			tab[i] = newNode(hash, key, value, null);
		else {
			Node<K,V> e; K k;
			// 判断第一个节点是否等于等于指定key
			if (p.hash == hash &&
					((k = p.key) == key || (key != null && key.equals(k))))
				e = p;
				// 如果第一个节点不等于指定key, 且是树节点, 则调用树的put方法
			else if (p instanceof TreeNode)
				e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
			else {
				for (int binCount = 0; ; ++binCount) {
					// 如果找到了链表的最后一个节点了都还没有找到元素, 就直接创建一个, 放到末尾
					if ((e = p.next) == null) {
						p.next = newNode(hash, key, value, null);
						// 如果这个链表中的元素已经达到了指定的临界值, 则转化为树
						if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
							treeifyBin(tab, hash);
						break;
					}
					// 如果我们找到了这个key, 则直接break
					if (e.hash == hash &&
							((k = e.key) == key || (key != null && key.equals(k))))
						break;
					p = e;
				}
			}
			// 如果我们找到了现有的一个key
			if (e != null) { // key的现有映射
				V oldValue = e.value;
				if (!onlyIfAbsent || oldValue == null)
					e.value = value;
				afterNodeAccess(e);// 调用LinkedHashMap的回调函数
				return oldValue;
			}
		}
		// 改变次数加1
		++modCount;
		// 如果容量达到了指定值则resize
		if (++size > threshold)
			resize();
		// 调用LinkedHashMap的回调函数
		afterNodeInsertion(evict);
		return null;
	}

	/**
	 * 初始化或加倍table的大小. 如果为null, 则按照字段阈值中持有的初始容量目标
	 * 分配. 否则, 因为我们使用的是2的幂展开, 所以每个bin中的元素要么必须保持
	 * 相同的索引, 要么在新表中以2的幂偏移量移动.
	 *
	 * @return the table
	 */
	final Node<K,V>[] resize() {
		// 记录旧table、旧table长度、旧扩容个阈值
		Node<K,V>[] oldTab = table;
		int oldCap = (oldTab == null) ? 0 : oldTab.length;
		int oldThr = threshold;
		int newCap, newThr = 0;
		// 如果旧table长度大于0
		if (oldCap > 0) {
			// 如果旧table长度已经达到了最大值, 直接不扩容了
			if (oldCap >= MAXIMUM_CAPACITY) {
				threshold = Integer.MAX_VALUE;
				return oldTab;
			}
			// 如果旧table长度乘以2任然小于最大长度, 旧table长度大于等于默认容量, 就扩容, 直接将长度乘以2
			else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
					oldCap >= DEFAULT_INITIAL_CAPACITY)
				newThr = oldThr << 1; // double threshold
		}
		// 如果旧table长度小于等于0(其实就是刚创建好, 还没有放入东西就开始resize, 就是使用其他Map创建新HashMap的情况)
		else if (oldThr > 0) // 初始容量设置为threshold
			newCap = oldThr;
		else {               // 初始threshold为0表示使用默认值
			newCap = DEFAULT_INITIAL_CAPACITY;
			newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
		}
		// 如果算了半天没有算出来新阈值, 则我们就使用负载因子计算一个出来
		if (newThr == 0) {
			float ft = (float)newCap * loadFactor;
			newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
					(int)ft : Integer.MAX_VALUE);
		}
		threshold = newThr;
		@SuppressWarnings({"rawtypes","unchecked"})
		Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
		table = newTab;
		if (oldTab != null) {
			// 遍历就table
			for (int j = 0; j < oldCap; ++j) {
				Node<K,V> e;
				// 如果旧table的某个元素不为null才处理
				if ((e = oldTab[j]) != null) {
					// 我们立刻就把旧table的元素置为null
					oldTab[j] = null;
					// 如果这个元素没有下一个元素(意思就是只有它自己一个元素, 直接重新计算其在新table中的索引即可)
					if (e.next == null)
						newTab[e.hash & (newCap - 1)] = e;
						// 如果有多个元素, 并且是树容器, 直接调用树的方法进行拆分
					else if (e instanceof TreeNode)
						((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
						// 如果是链表就很好处理了, 直接把原来的容器拆分为两个容器即可
						// 因为我们采取的是hash & (容量 - 1)这种方式来计算索引的, 而且扩容的时候都是旧table长度乘以2
						// 这种扩容方式可以保证在进行&运算的时候, 容量在乘以2之前和之后, 计算结果的低位都是一样的
						// 只有高位可能为1或为0, 当高位为0的时候, 计算出来的索引还是在原来的位置, 即索引不变
						// 当高位为1的时候, 这个多出来的1其值恰好就是旧table长度, 所以其新索引为 原索引值+旧table长度
						// 所以其实我们将原来的链表、树表拆分为两个就可以了, 高位1个, 低位一个
					else { // preserve order
						Node<K,V> loHead = null, loTail = null;
						Node<K,V> hiHead = null, hiTail = null;
						Node<K,V> next;
						do {
							next = e.next;
							if ((e.hash & oldCap) == 0) {
								if (loTail == null)
									loHead = e;
								else
									loTail.next = e;
								loTail = e;
							}
							else {
								if (hiTail == null)
									hiHead = e;
								else
									hiTail.next = e;
								hiTail = e;
							}
						} while ((e = next) != null);
						if (loTail != null) {
							loTail.next = null;
							newTab[j] = loHead;
						}
						if (hiTail != null) {
							hiTail.next = null;
							newTab[j + oldCap] = hiHead;
						}
					}
				}
			}
		}
		return newTab;
	}

	/**
	 * Replaces all linked nodes in bin at index for given hash unless
	 * table is too small, in which case resizes instead.
	 */
	final void treeifyBin(Node<K,V>[] tab, int hash) {
		int n, index; Node<K,V> e;
		// 如果表不存在或表的长度小于
		if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
			resize();
		else if ((e = tab[index = (n - 1) & hash]) != null) {
			// hd为head头节点, tl为tile尾节点
			TreeNode<K,V> hd = null, tl = null;
			// 这段代码就干了一件事, 将原来链表节点的prev、next关系全部复制到树中, 并且把head节点记录下来
			do {
				TreeNode<K,V> p = replacementTreeNode(e, null);
				if (tl == null)
					hd = p;
				else {
					p.prev = tl;
					tl.next = p;
				}
				tl = p;
			} while ((e = e.next) != null);
			// 把table中指定位置的元素替换为树元素, 并调用树元素的treeify转化为树
			if ((tab[index] = hd) != null)
				hd.treeify(tab);
		}
	}

	/**
	 * 将所有映射从指定map复制到此map.
	 * 这些映射将替换此map对当前指定map中的任何key所具有的任何映射.
	 *
	 * @param m 要存储在此map中的映射
	 * @throws NullPointerException 如果指定的map为null
	 */
	public void putAll(Map<? extends K, ? extends V> m) {
		putMapEntries(m, true);
	}

	/**
	 * 如果存在, 则从此map中移除指定key的映射.
	 *
	 * @param  key 要将其映射从map中移除的key
	 * @return 与<tt>key</tt>关联的前一个值, 如果<tt>key</tt>没有映射, 则为
	 *         <tt>null</tt>. (<tt>null</tt>返回还可以指示map先前将
	 *         <tt>null</tt>与<tt>key</tt>关联.)
	 */
	public V remove(Object key) {
		Node<K,V> e;
		return (e = removeNode(hash(key), key, null, false, true)) == null ?
				null : e.value;
	}

	/**
	 * 实现了Map.remove及相关方法
	 *
	 * @param hash hash for key
	 * @param key the key
	 * @param value 如果matchValue, 则要匹配的值, 否则忽略
	 * @param matchValue 如果为true, 则仅在值相等时删除
	 * @param movable 如果为false, 则在删除时不要移动其他节点
	 * @return node, 如果没有则为null
	 */
	final Node<K,V> removeNode(int hash, Object key, Object value,
	                           boolean matchValue, boolean movable) {
		Node<K,V>[] tab; Node<K,V> p; int n, index;
		// table不为null, table长度不为0, key的hash值在table中映射的索引有数据
		// 总之, 在这个key有可能存在value的情况下才去进行操作
		if ((tab = table) != null && (n = tab.length) > 0 &&
				(p = tab[index = (n - 1) & hash]) != null) {
			Node<K,V> node = null, e; K k; V v;
			// 如果第一个元素就是满足条件
			if (p.hash == hash &&
					((k = p.key) == key || (key != null && key.equals(k))))
				node = p;
				// 如果第一个元素不满足条件, 但是存在下一个元素
			else if ((e = p.next) != null) {
				// 如果这是一棵树, 则调用树的方法去找我们要删除的节点
				if (p instanceof TreeNode)
					node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
					// 如果这是一个链表, 则使用不断循环下一个节点, 找到我们要删除的那个
				else {
					do {
						if (e.hash == hash &&
								((k = e.key) == key ||
										(key != null && key.equals(k)))) {
							node = e;
							break;
						}
						p = e;
					} while ((e = e.next) != null);
				}
			}
			// 如果我们找到了要删除的节点
			if (node != null && (!matchValue || (v = node.value) == value ||
					(value != null && value.equals(v)))) {
				// 如果是树, 则调用树的方法去删除
				if (node instanceof TreeNode)
					((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
					// 如果第一个节点就是要删除的那个
				else if (node == p)
					tab[index] = node.next;
					// 如果是链表, 则采用链表的删除方式
				else
					p.next = node.next;
				++modCount;
				--size;
				afterNodeRemoval(node);
				return node;
			}
		}
		return null;
	}

	/**
	 * 从此map中删除所有映射.
	 * 此调用返回之后, map将为空.
	 */
	public void clear() {
		Node<K,V>[] tab;
		modCount++;
		if ((tab = table) != null && size > 0) {
			size = 0;
			for (int i = 0; i < tab.length; ++i)
				tab[i] = null;
		}
	}

	/**
	 * 如果此map将一个或多个key映射到指定value, 则返回<tt>true</tt>.
	 *
	 * @param value 要测其在该map中的存在的value
	 * @return <tt>true</tt> 如果该map将一个或多个key映射到指定value
	 */
	public boolean containsValue(Object value) {
		Node<K,V>[] tab; V v;
		if ((tab = table) != null && size > 0) {
			// 遍历table中的每个元素
			for (int i = 0; i < tab.length; ++i) {
				// table的元素, 不管是不是树, 其实都有next指针, 都可以当成链表处理
				for (Node<K,V> e = tab[i]; e != null; e = e.next) {
					if ((v = e.value) == value ||
							(value != null && value.equals(v)))
						return true;
				}
			}
		}
		return false;
	}

	/**
	 * 返回此map中包含的key的{@link Set} view. set由map支持, 因此对map的更改
	 * 将反映在set中, 反之亦反. 如果map在对set进行迭代时被修改(iterator自己的
	 * <tt>remove</tt>操作除外), 迭代的结果是未定的. 方法从map中删除相应的映射,
	 * 该set支持元素删除, 即通过<tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
	 * <tt>removeAll</tt>, <tt>retainAll</tt>和<tt>clear</tt>操作从map
	 * 中删除相应的映射. 不支持<tt>add</tt>或<tt>addAll</tt>操作.
	 *
	 * @return 此map中包含的key的set view
	 */
	public Set<K> keySet() {
		Set<K> ks = keySet;
		if (ks == null) {
			ks = new KeySet();
			keySet = ks;
		}
		return ks;
	}

	// KeySet也是一个真实的Set, 只不过是进行了适配, 其某些方法由HashMap去实现
	final class KeySet extends AbstractSet<K> {
		public final int size()                 { return size; }
		public final void clear()               { HashMap.this.clear(); }
		public final Iterator<K> iterator()     { return new KeyIterator(); }
		public final boolean contains(Object o) { return containsKey(o); }
		public final boolean remove(Object key) {
			return removeNode(hash(key), key, null, false, true) != null;
		}
		public final Spliterator<K> spliterator() {
			return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
		}
		// 遍历
		public final void forEach(Consumer<? super K> action) {
			Node<K,V>[] tab;
			if (action == null)
				throw new NullPointerException();
			if (size > 0 && (tab = table) != null) {
				int mc = modCount;
				for (int i = 0; i < tab.length; ++i) {
					for (Node<K,V> e = tab[i]; e != null; e = e.next)
						action.accept(e.key);
				}
				if (modCount != mc)
					throw new ConcurrentModificationException();
			}
		}
	}

	/**
	 * 返回此map中包含的values的{@link Collection} view. collection由map支持,
	 * 因此对map操作会反映在collection中, 反之亦然. 如果在对collection进行迭代时
	 * 修改了map(iterator自己的<tt>remove</tt>操作除外), 则迭代的结果是未定义的.
	 * collection支持元素删除, 即通过<tt>Iterator.remove</tt>,
	 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
	 * <tt>retainAll</tt>和<tt>clear</tt>操作从map中删除相应的映射. 不支持
	 * <tt>add</tt>或<tt>addAll</tt>操作.
	 *
	 * @return 此map中包含的values的view
	 */
	public Collection<V> values() {
		Collection<V> vs = values;
		if (vs == null) {
			vs = new Values();
			values = vs;
		}
		return vs;
	}

	final class Values extends AbstractCollection<V> {
		public final int size()                 { return size; }
		public final void clear()               { HashMap.this.clear(); }
		public final Iterator<V> iterator()     { return new ValueIterator(); }
		public final boolean contains(Object o) { return containsValue(o); }
		public final Spliterator<V> spliterator() {
			return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
		}
		public final void forEach(Consumer<? super V> action) {
			Node<K,V>[] tab;
			if (action == null)
				throw new NullPointerException();
			if (size > 0 && (tab = table) != null) {
				int mc = modCount;
				for (int i = 0; i < tab.length; ++i) {
					for (Node<K,V> e = tab[i]; e != null; e = e.next)
						action.accept(e.value);
				}
				if (modCount != mc)
					throw new ConcurrentModificationException();
			}
		}
	}

	/**
	 * 返回此map中包含的映射的{@link Set} view. set由map支持, 因此对map的更改
	 * 将反映在set中, 反之亦然. 如果在迭代集合的过程中修改了map(除了通过iterator
	 * 自己的<tt>remove</tt>操作, 或者通过iterator返回的映射条目上的<tt>setValue</tt>
	 * 操作), 则迭代的结果是未定义的. 该set支持元素删除, 即通过<tt>Iterator.remove</tt>,
	 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>和<tt>clear</tt>
	 * 操作从map中删除相应的映射. 不支持<tt>add</tt>或<tt>addAll</tt>操作.
	 *
	 * @return 此map中包含的映射的set view
	 */
	public Set<Map.Entry<K,V>> entrySet() {
		Set<Map.Entry<K,V>> es;
		return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
	}

	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
		public final int size()                 { return size; }
		public final void clear()               { HashMap.this.clear(); }
		public final Iterator<Map.Entry<K,V>> iterator() {
			return new EntryIterator();
		}
		public final boolean contains(Object o) {
			if (!(o instanceof Map.Entry))
				return false;
			Map.Entry<?,?> e = (Map.Entry<?,?>) o;
			Object key = e.getKey();
			Node<K,V> candidate = getNode(hash(key), key);
			return candidate != null && candidate.equals(e);
		}
		public final boolean remove(Object o) {
			if (o instanceof Map.Entry) {
				Map.Entry<?,?> e = (Map.Entry<?,?>) o;
				Object key = e.getKey();
				Object value = e.getValue();
				return removeNode(hash(key), key, value, true, true) != null;
			}
			return false;
		}
		public final Spliterator<Map.Entry<K,V>> spliterator() {
			return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
		}
		public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
			Node<K,V>[] tab;
			if (action == null)
				throw new NullPointerException();
			if (size > 0 && (tab = table) != null) {
				int mc = modCount;
				for (int i = 0; i < tab.length; ++i) {
					for (Node<K,V> e = tab[i]; e != null; e = e.next)
						action.accept(e);
				}
				if (modCount != mc)
					throw new ConcurrentModificationException();
			}
		}
	}

	// Overrides of JDK8 Map extension methods

	@Override
	public V getOrDefault(Object key, V defaultValue) {
		Node<K,V> e;
		return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
	}

	@Override
	public V putIfAbsent(K key, V value) {
		return putVal(hash(key), key, value, true, true);
	}

	@Override
	public boolean remove(Object key, Object value) {
		return removeNode(hash(key), key, value, true, true) != null;
	}

	@Override
	public boolean replace(K key, V oldValue, V newValue) {
		Node<K,V> e; V v;
		if ((e = getNode(hash(key), key)) != null &&
				((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
			e.value = newValue;
			afterNodeAccess(e);
			return true;
		}
		return false;
	}

	@Override
	public V replace(K key, V value) {
		Node<K,V> e;
		if ((e = getNode(hash(key), key)) != null) {
			V oldValue = e.value;
			e.value = value;
			afterNodeAccess(e);
			return oldValue;
		}
		return null;
	}

	@Override
	public V computeIfAbsent(K key,
	                         Function<? super K, ? extends V> mappingFunction) {
		if (mappingFunction == null)
			throw new NullPointerException();
		int hash = hash(key);
		Node<K,V>[] tab; Node<K,V> first; int n, i;
		int binCount = 0;
		TreeNode<K,V> t = null;
		Node<K,V> old = null;
		if (size > threshold || (tab = table) == null ||
				(n = tab.length) == 0)
			n = (tab = resize()).length;
		if ((first = tab[i = (n - 1) & hash]) != null) {
			if (first instanceof TreeNode)
				old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
			else {
				Node<K,V> e = first; K k;
				do {
					if (e.hash == hash &&
							((k = e.key) == key || (key != null && key.equals(k)))) {
						old = e;
						break;
					}
					++binCount;
				} while ((e = e.next) != null);
			}
			V oldValue;
			if (old != null && (oldValue = old.value) != null) {
				afterNodeAccess(old);
				return oldValue;
			}
		}
		V v = mappingFunction.apply(key);
		if (v == null) {
			return null;
		} else if (old != null) {
			old.value = v;
			afterNodeAccess(old);
			return v;
		}
		else if (t != null)
			t.putTreeVal(this, tab, hash, key, v);
		else {
			tab[i] = newNode(hash, key, v, first);
			if (binCount >= TREEIFY_THRESHOLD - 1)
				treeifyBin(tab, hash);
		}
		++modCount;
		++size;
		afterNodeInsertion(true);
		return v;
	}

	public V computeIfPresent(K key,
	                          BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
		if (remappingFunction == null)
			throw new NullPointerException();
		Node<K,V> e; V oldValue;
		int hash = hash(key);
		if ((e = getNode(hash, key)) != null &&
				(oldValue = e.value) != null) {
			V v = remappingFunction.apply(key, oldValue);
			if (v != null) {
				e.value = v;
				afterNodeAccess(e);
				return v;
			}
			else
				removeNode(hash, key, null, false, true);
		}
		return null;
	}

	@Override
	public V compute(K key,
	                 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
		if (remappingFunction == null)
			throw new NullPointerException();
		int hash = hash(key);
		Node<K,V>[] tab; Node<K,V> first; int n, i;
		int binCount = 0;
		TreeNode<K,V> t = null;
		Node<K,V> old = null;
		if (size > threshold || (tab = table) == null ||
				(n = tab.length) == 0)
			n = (tab = resize()).length;
		if ((first = tab[i = (n - 1) & hash]) != null) {
			if (first instanceof TreeNode)
				old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
			else {
				Node<K,V> e = first; K k;
				do {
					if (e.hash == hash &&
							((k = e.key) == key || (key != null && key.equals(k)))) {
						old = e;
						break;
					}
					++binCount;
				} while ((e = e.next) != null);
			}
		}
		V oldValue = (old == null) ? null : old.value;
		V v = remappingFunction.apply(key, oldValue);
		if (old != null) {
			if (v != null) {
				old.value = v;
				afterNodeAccess(old);
			}
			else
				removeNode(hash, key, null, false, true);
		}
		else if (v != null) {
			if (t != null)
				t.putTreeVal(this, tab, hash, key, v);
			else {
				tab[i] = newNode(hash, key, v, first);
				if (binCount >= TREEIFY_THRESHOLD - 1)
					treeifyBin(tab, hash);
			}
			++modCount;
			++size;
			afterNodeInsertion(true);
		}
		return v;
	}

	@Override
	public V merge(K key, V value,
	               BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
		if (value == null)
			throw new NullPointerException();
		if (remappingFunction == null)
			throw new NullPointerException();
		int hash = hash(key);
		Node<K,V>[] tab; Node<K,V> first; int n, i;
		int binCount = 0;
		TreeNode<K,V> t = null;
		Node<K,V> old = null;
		if (size > threshold || (tab = table) == null ||
				(n = tab.length) == 0)
			n = (tab = resize()).length;
		if ((first = tab[i = (n - 1) & hash]) != null) {
			if (first instanceof TreeNode)
				old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
			else {
				Node<K,V> e = first; K k;
				do {
					if (e.hash == hash &&
							((k = e.key) == key || (key != null && key.equals(k)))) {
						old = e;
						break;
					}
					++binCount;
				} while ((e = e.next) != null);
			}
		}
		if (old != null) {
			V v;
			if (old.value != null)
				v = remappingFunction.apply(old.value, value);
			else
				v = value;
			if (v != null) {
				old.value = v;
				afterNodeAccess(old);
			}
			else
				removeNode(hash, key, null, false, true);
			return v;
		}
		if (value != null) {
			if (t != null)
				t.putTreeVal(this, tab, hash, key, value);
			else {
				tab[i] = newNode(hash, key, value, first);
				if (binCount >= TREEIFY_THRESHOLD - 1)
					treeifyBin(tab, hash);
			}
			++modCount;
			++size;
			afterNodeInsertion(true);
		}
		return value;
	}

	@Override
	public void forEach(BiConsumer<? super K, ? super V> action) {
		Node<K,V>[] tab;
		if (action == null)
			throw new NullPointerException();
		if (size > 0 && (tab = table) != null) {
			int mc = modCount;
			for (int i = 0; i < tab.length; ++i) {
				for (Node<K,V> e = tab[i]; e != null; e = e.next)
					action.accept(e.key, e.value);
			}
			if (modCount != mc)
				throw new ConcurrentModificationException();
		}
	}

	@Override
	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
		Node<K,V>[] tab;
		if (function == null)
			throw new NullPointerException();
		if (size > 0 && (tab = table) != null) {
			int mc = modCount;
			for (int i = 0; i < tab.length; ++i) {
				for (Node<K,V> e = tab[i]; e != null; e = e.next) {
					e.value = function.apply(e.key, e.value);
				}
			}
			if (modCount != mc)
				throw new ConcurrentModificationException();
		}
	}

	/* ------------------------------------------------------------ */
	// Cloning and serialization

	/**
	 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
	 * values themselves are not cloned.
	 *
	 * @return a shallow copy of this map
	 */
	@SuppressWarnings("unchecked")
	@Override
	public Object clone() {
		HashMap<K,V> result;
		try {
			result = (HashMap<K,V>)super.clone();
		} catch (CloneNotSupportedException e) {
			// this shouldn't happen, since we are Cloneable
			throw new InternalError(e);
		}
		result.reinitialize();
		result.putMapEntries(this, false);
		return result;
	}

	// These methods are also used when serializing HashSets
	final float loadFactor() { return loadFactor; }
	final int capacity() {
		return (table != null) ? table.length :
				(threshold > 0) ? threshold :
						DEFAULT_INITIAL_CAPACITY;
	}

	/**
	 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
	 * serialize it).
	 *
	 * @serialData The <i>capacity</i> of the HashMap (the length of the
	 *             bucket array) is emitted (int), followed by the
	 *             <i>size</i> (an int, the number of key-value
	 *             mappings), followed by the key (Object) and value (Object)
	 *             for each key-value mapping.  The key-value mappings are
	 *             emitted in no particular order.
	 */
	private void writeObject(java.io.ObjectOutputStream s)
			throws IOException {
		int buckets = capacity();
		// Write out the threshold, loadfactor, and any hidden stuff
		s.defaultWriteObject();
		s.writeInt(buckets);
		s.writeInt(size);
		internalWriteEntries(s);
	}

	/**
	 * Reconstitute the {@code HashMap} instance from a stream (i.e.,
	 * deserialize it).
	 */
	private void readObject(java.io.ObjectInputStream s)
			throws IOException, ClassNotFoundException {
		// Read in the threshold (ignored), loadfactor, and any hidden stuff
		s.defaultReadObject();
		reinitialize();
		if (loadFactor <= 0 || Float.isNaN(loadFactor))
			throw new InvalidObjectException("Illegal load factor: " +
					loadFactor);
		s.readInt();                // Read and ignore number of buckets
		int mappings = s.readInt(); // Read number of mappings (size)
		if (mappings < 0)
			throw new InvalidObjectException("Illegal mappings count: " +
					mappings);
		else if (mappings > 0) { // (if zero, use defaults)
			// Size the table using given load factor only if within
			// range of 0.25...4.0
			float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
			float fc = (float)mappings / lf + 1.0f;
			int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
					DEFAULT_INITIAL_CAPACITY :
					(fc >= MAXIMUM_CAPACITY) ?
							MAXIMUM_CAPACITY :
							tableSizeFor((int)fc));
			float ft = (float)cap * lf;
			threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
					(int)ft : Integer.MAX_VALUE);

			// Check Map.Entry[].class since it's the nearest public type to
			// what we're actually creating.
			SharedSecrets.getJavaOISAccess().checkArray(s, Map.Entry[].class, cap);
			@SuppressWarnings({"rawtypes","unchecked"})
			Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
			table = tab;

			// Read the keys and values, and put the mappings in the HashMap
			for (int i = 0; i < mappings; i++) {
				@SuppressWarnings("unchecked")
				K key = (K) s.readObject();
				@SuppressWarnings("unchecked")
				V value = (V) s.readObject();
				putVal(hash(key), key, value, false, false);
			}
		}
	}

	/* ------------------------------------------------------------ */
	// iterators

	abstract class HashIterator {
		Node<K,V> next;        // 下一个要返回的条目
		Node<K,V> current;     // 当前条目
		int expectedModCount;  // 用于快速失败
		int index;             // 当前位置

		HashIterator() {
			expectedModCount = modCount;
			Node<K,V>[] t = table;
			current = next = null;
			index = 0;
			if (t != null && size > 0) { // advance to first entry进入第一个入口(找到一个不为null的数组元素)
				do {} while (index < t.length && (next = t[index++]) == null);
			}
		}

		public final boolean hasNext() {
			return next != null;
		}

		final Node<K,V> nextNode() {
			Node<K,V>[] t;
			Node<K,V> e = next;
			// 快速失败
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();
			if (e == null)
				throw new NoSuchElementException();
			// 如果这个next上有下一个节点直接获取这个节点, 否则继续从下一个不为null的table元素上查找
			if ((next = (current = e).next) == null && (t = table) != null) {
				do {} while (index < t.length && (next = t[index++]) == null);
			}
			return e;
		}

		// 删除不会传参, 删除只是删除当前元素
		public final void remove() {
			Node<K,V> p = current;
			if (p == null)
				throw new IllegalStateException();
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();
			current = null;
			K key = p.key;
			removeNode(hash(key), key, null, false, false);
			expectedModCount = modCount;
		}
	}

	// 从下面三个具体的Iterator可以看出来, 三个Iterator共用了nextNode, 设计很巧妙

	// HashIterator已经很完善了, 只是next还没实现
	final class KeyIterator extends HashIterator
			implements Iterator<K> {
		public final K next() { return nextNode().key; }
	}

	// HashIterator已经很完善了, 只是next还没实现
	final class ValueIterator extends HashIterator
			implements Iterator<V> {
		public final V next() { return nextNode().value; }
	}

	// HashIterator已经很完善了, 只是next还没实现
	final class EntryIterator extends HashIterator
			implements Iterator<Map.Entry<K,V>> {
		public final Map.Entry<K,V> next() { return nextNode(); }
	}

	/* ------------------------------------------------------------ */
	// spliterators

	static class HashMapSpliterator<K,V> {
		final HashMap<K,V> map;
		Node<K,V> current;          // current node
		int index;                  // current index, modified on advance/split
		int fence;                  // one past last index
		int est;                    // size estimate
		int expectedModCount;       // for comodification checks

		HashMapSpliterator(HashMap<K,V> m, int origin,
		                   int fence, int est,
		                   int expectedModCount) {
			this.map = m;
			this.index = origin;
			this.fence = fence;
			this.est = est;
			this.expectedModCount = expectedModCount;
		}

		final int getFence() { // initialize fence and size on first use
			int hi;
			if ((hi = fence) < 0) {
				HashMap<K,V> m = map;
				est = m.size;
				expectedModCount = m.modCount;
				Node<K,V>[] tab = m.table;
				hi = fence = (tab == null) ? 0 : tab.length;
			}
			return hi;
		}

		public final long estimateSize() {
			getFence(); // force init
			return (long) est;
		}
	}

	static final class KeySpliterator<K,V>
			extends HashMapSpliterator<K,V>
			implements Spliterator<K> {
		KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,
		               int expectedModCount) {
			super(m, origin, fence, est, expectedModCount);
		}

		public KeySpliterator<K,V> trySplit() {
			int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
			return (lo >= mid || current != null) ? null :
					new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
							expectedModCount);
		}

		public void forEachRemaining(Consumer<? super K> action) {
			int i, hi, mc;
			if (action == null)
				throw new NullPointerException();
			HashMap<K,V> m = map;
			Node<K,V>[] tab = m.table;
			if ((hi = fence) < 0) {
				mc = expectedModCount = m.modCount;
				hi = fence = (tab == null) ? 0 : tab.length;
			}
			else
				mc = expectedModCount;
			if (tab != null && tab.length >= hi &&
					(i = index) >= 0 && (i < (index = hi) || current != null)) {
				Node<K,V> p = current;
				current = null;
				do {
					if (p == null)
						p = tab[i++];
					else {
						action.accept(p.key);
						p = p.next;
					}
				} while (p != null || i < hi);
				if (m.modCount != mc)
					throw new ConcurrentModificationException();
			}
		}

		public boolean tryAdvance(Consumer<? super K> action) {
			int hi;
			if (action == null)
				throw new NullPointerException();
			Node<K,V>[] tab = map.table;
			if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
				while (current != null || index < hi) {
					if (current == null)
						current = tab[index++];
					else {
						K k = current.key;
						current = current.next;
						action.accept(k);
						if (map.modCount != expectedModCount)
							throw new ConcurrentModificationException();
						return true;
					}
				}
			}
			return false;
		}

		public int characteristics() {
			return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
					Spliterator.DISTINCT;
		}
	}

	static final class ValueSpliterator<K,V>
			extends HashMapSpliterator<K,V>
			implements Spliterator<V> {
		ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,
		                 int expectedModCount) {
			super(m, origin, fence, est, expectedModCount);
		}

		public ValueSpliterator<K,V> trySplit() {
			int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
			return (lo >= mid || current != null) ? null :
					new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
							expectedModCount);
		}

		public void forEachRemaining(Consumer<? super V> action) {
			int i, hi, mc;
			if (action == null)
				throw new NullPointerException();
			HashMap<K,V> m = map;
			Node<K,V>[] tab = m.table;
			if ((hi = fence) < 0) {
				mc = expectedModCount = m.modCount;
				hi = fence = (tab == null) ? 0 : tab.length;
			}
			else
				mc = expectedModCount;
			if (tab != null && tab.length >= hi &&
					(i = index) >= 0 && (i < (index = hi) || current != null)) {
				Node<K,V> p = current;
				current = null;
				do {
					if (p == null)
						p = tab[i++];
					else {
						action.accept(p.value);
						p = p.next;
					}
				} while (p != null || i < hi);
				if (m.modCount != mc)
					throw new ConcurrentModificationException();
			}
		}

		public boolean tryAdvance(Consumer<? super V> action) {
			int hi;
			if (action == null)
				throw new NullPointerException();
			Node<K,V>[] tab = map.table;
			if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
				while (current != null || index < hi) {
					if (current == null)
						current = tab[index++];
					else {
						V v = current.value;
						current = current.next;
						action.accept(v);
						if (map.modCount != expectedModCount)
							throw new ConcurrentModificationException();
						return true;
					}
				}
			}
			return false;
		}

		public int characteristics() {
			return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
		}
	}

	static final class EntrySpliterator<K,V>
			extends HashMapSpliterator<K,V>
			implements Spliterator<Map.Entry<K,V>> {
		EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
		                 int expectedModCount) {
			super(m, origin, fence, est, expectedModCount);
		}

		public EntrySpliterator<K,V> trySplit() {
			int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
			return (lo >= mid || current != null) ? null :
					new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
							expectedModCount);
		}

		public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
			int i, hi, mc;
			if (action == null)
				throw new NullPointerException();
			HashMap<K,V> m = map;
			Node<K,V>[] tab = m.table;
			if ((hi = fence) < 0) {
				mc = expectedModCount = m.modCount;
				hi = fence = (tab == null) ? 0 : tab.length;
			}
			else
				mc = expectedModCount;
			if (tab != null && tab.length >= hi &&
					(i = index) >= 0 && (i < (index = hi) || current != null)) {
				Node<K,V> p = current;
				current = null;
				do {
					if (p == null)
						p = tab[i++];
					else {
						action.accept(p);
						p = p.next;
					}
				} while (p != null || i < hi);
				if (m.modCount != mc)
					throw new ConcurrentModificationException();
			}
		}

		public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
			int hi;
			if (action == null)
				throw new NullPointerException();
			Node<K,V>[] tab = map.table;
			if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
				while (current != null || index < hi) {
					if (current == null)
						current = tab[index++];
					else {
						Node<K,V> e = current;
						current = current.next;
						action.accept(e);
						if (map.modCount != expectedModCount)
							throw new ConcurrentModificationException();
						return true;
					}
				}
			}
			return false;
		}

		public int characteristics() {
			return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
					Spliterator.DISTINCT;
		}
	}

	/* ------------------------------------------------------------ */
	// LinkedHashMap support


	/*
	 * The following package-protected methods are designed to be
	 * overridden by LinkedHashMap, but not by any other subclass.
	 * Nearly all other internal methods are also package-protected
	 * but are declared final, so can be used by LinkedHashMap, view
	 * classes, and HashSet.
	 */

	// Create a regular (non-tree) node
	Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
		return new Node<>(hash, key, value, next);
	}

	// For conversion from TreeNodes to plain nodes
	Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
		return new Node<>(p.hash, p.key, p.value, next);
	}

	// Create a tree bin node
	TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
		return new TreeNode<>(hash, key, value, next);
	}

	// For treeifyBin
	TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
		return new TreeNode<>(p.hash, p.key, p.value, next);
	}

	/**
	 * Reset to initial default state.  Called by clone and readObject.
	 */
	void reinitialize() {
		table = null;
		entrySet = null;
		keySet = null;
		values = null;
		modCount = 0;
		threshold = 0;
		size = 0;
	}

	// Callbacks to allow LinkedHashMap post-actions
	void afterNodeAccess(Node<K,V> p) { }
	void afterNodeInsertion(boolean evict) { }
	void afterNodeRemoval(Node<K,V> p) { }

	// Called only from writeObject, to ensure compatible ordering.
	void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
		Node<K,V>[] tab;
		if (size > 0 && (tab = table) != null) {
			for (int i = 0; i < tab.length; ++i) {
				for (Node<K,V> e = tab[i]; e != null; e = e.next) {
					s.writeObject(e.key);
					s.writeObject(e.value);
				}
			}
		}
	}

	/* ------------------------------------------------------------ */
	// Tree bins

	/**
	 * 树容器入口. 扩展LinkedHashMap.Entry (它又扩展Node),
	 * 因此可以用作常规节点或linked节点的扩展.
	 */
	static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
		TreeNode<K,V> parent;  // red-black树的链接
		TreeNode<K,V> left;
		TreeNode<K,V> right;
		TreeNode<K,V> prev;    // 需要在删除时断开下一个链接
		boolean red;
		// 初始化时仅仅只是初始化了一个当前节点, 剩下的next节点这些都是传入的
		// parent、left、right这些都没有确定, 都是后面调用其他方法计算出来的
		TreeNode(int hash, K key, V val, Node<K,V> next) {
			super(hash, key, val, next);
		}

		/**
		 * 返回包含此节点的树的root.
		 */
		final TreeNode<K,V> root() {
			for (TreeNode<K,V> r = this, p;;) {
				if ((p = r.parent) == null)
					return r;
				r = p;
			}
		}

		/**
		 * 确保给定的root是其bin的第一个节点.
		 */
		static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
			int n;
			if (root != null && tab != null && (n = tab.length) > 0) {
				int index = (n - 1) & root.hash;
				// 从数组中取出第一个元素
				TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
				// 如果第一个元素不是我们指定的root, 那么我们就要进行调整了
				if (root != first) {
					Node<K,V> rn;
					// 将指定的root元素放到数组中去
					tab[index] = root;
					// 以下几步操作说白了就是将当前的root元素从之前它所在的双向链表里面删掉
					TreeNode<K,V> rp = root.prev;
					if ((rn = root.next) != null)
						((TreeNode<K,V>)rn).prev = rp;
					if (rp != null)
						rp.next = rn;
					// 一下的几步操作说白了就是把当前的root节点放在原来的first节点的前面
					if (first != null)
						first.prev = root;
					root.next = first;
					root.prev = null;
				}
				assert checkInvariants(root);
			}
		}

		/**
		 * 使用给定的hash和key从根p开始查找节点.
		 * key参数在首次使用比较key时缓存comparableClassFor(key).
		 * @param h  要寻找的key的hash值(经过抗扰动计算)
		 * @param k  要寻找的key
		 * @param kc 要寻找的key的类型
		 * @return
		 */
		final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
			TreeNode<K,V> p = this;
			do {
				// ph当前节点的hash值、pk当前节点的key值
				int ph, dir; K pk;
				// pl当前节点的左孩子、pr当前节点的右孩子
				TreeNode<K,V> pl = p.left, pr = p.right, q;
				// 既然hash值比左孩子的小, 那就从左子树中去找吧
				if ((ph = p.hash) > h)
					p = pl;
				// 既然hash值比右孩子的大, 那就从右子树中去找吧
				else if (ph < h)
					p = pr;
				// 既然不大也不小, 是相等的, 那就是找到了
				else if ((pk = p.key) == k || (k != null && k.equals(pk)))
					return p;
				// 如果hash值相等了, 但是==和equals判断不等, 而且这个时候也没有左孩子了, 那就去右子树上找
				else if (pl == null)
					p = pr;
				// 如果hash值相等了, 但是==和equals判断不等, 而且这个时候也没有右孩子了, 那就去左子树上找
				else if (pr == null)
					p = pl;
				// 如果hash值相等了, 但是==和equals判断不等, 而且左右孩子都不为null, 比较一下看该去左子树还是右子树上找吧
				else if ((kc != null ||
						(kc = comparableClassFor(k)) != null) &&
						(dir = compareComparables(kc, k, pk)) != 0)
					p = (dir < 0) ? pl : pr;
				// 比完了还是相等, 那没有什么说的了, 去右子树上找找看
				else if ((q = pr.find(h, k, kc)) != null)
					return q;
				// 右子树都 找不到还能怎么办, 去左边找吧
				else
					p = pl;
			} while (p != null);
			// 还找不到那就放弃了
			return null;
		}

		/**
		 * Calls find for root node.
		 */
		final TreeNode<K,V> getTreeNode(int h, Object k) {
			return ((parent != null) ? root() : this).find(h, k, null);
		}

		/**
		 * Tie-breaking utility for ordering insertions when equal
		 * hashCodes and non-comparable. We don't require a total
		 * order, just a consistent insertion rule to maintain
		 * equivalence across rebalancings. Tie-breaking further than
		 * necessary simplifies testing a bit.
		 */
		static int tieBreakOrder(Object a, Object b) {
			int d;
			if (a == null || b == null ||
					(d = a.getClass().getName().
							compareTo(b.getClass().getName())) == 0)
				d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
						-1 : 1);
			return d;
		}

		/**
		 * 形成从此节点开始链接节点树.
		 * @return 树根
		 */
		final void treeify(Node<K,V>[] tab) {
			TreeNode<K,V> root = null;
			// 整个操作说开了就是遍历整个链表节点, 链表的第一个节点作为根节点
			// 对于链表的其他节点我们直接从根节点开始查找插入位置, 插入完后进行平衡
			for (TreeNode<K,V> x = this, next; x != null; x = next) {
				next = (TreeNode<K,V>)x.next;
				// 将当前要处理的这个节点的左、右子树清空
				x.left = x.right = null;
				// 如果根节点不存在, 那么就把这个节点作为根节点
				// 根节点没有parent、并且是黑色的
				if (root == null) {
					x.parent = null;
					x.red = false;
					root = x;
				}
				// 根节点已经有了, 那我们就该处理其他节点了
				else {
					K k = x.key;
					int h = x.hash;
					Class<?> kc = null;
					// 从根节点开始遍历, 此遍历没有边界, 只能从内部退出
					for (TreeNode<K,V> p = root;;) {
						// dir标识方向(-1为左、1为右)、ph标识当前树节点的hash值
						int dir, ph;
						K pk = p.key;
						// 如果当前树节点的hash值大于当前链表节点的hash值
						if ((ph = p.hash) > h)
							// 标识当前链表节点会放在当前树节点的左边
							dir = -1;
						// 如果当前树节点的hash值小于当前链表节点的hash值
						else if (ph < h)
							// 标识当前链表节点会放在当前树节点的右边
							dir = 1;
						// 如果树节点和链表节点的hash值相等还要通过其他方式进行比较
						// 如果当前链表节点的key实现了Comparable接口, 并且链表节点具有相同类, 则通过Comparable接口进行比较
						// 否则调用tieBreakOrder进行比较
						else if ((kc == null &&
								(kc = comparableClassFor(k)) == null) ||
								(dir = compareComparables(kc, k, pk)) == 0)
							dir = tieBreakOrder(k, pk);

						// 保存当前树节点
						TreeNode<K,V> xp = p;
						// 如果dir为-1, 那么这个节点应该保存在当前树节点的左边, 但不一定是左孩子, 也有可能是左孩子的右孩子或者更深层次的节点
						// 如果dir为 1, 那么这个节点应该保存在当前树节点的右边, 但不一定是右孩子, 也有可能是右孩子的左孩子或者更深层次的节点
						// 如果当前左/右子树为null, 那么我们直接把当前链表节点放到该放的位置即可, 放的时候设置parent属性、调整树让树平衡
						// 如果当前左/右子树不为null, 那么好, 我们这边已经设置了p=p.left或right, 直接开启下一波循环吧
						// 说白了新节点的插入必须插在叶子节点上
						if ((p = (dir <= 0) ? p.left : p.right) == null) {
							x.parent = xp;
							if (dir <= 0)
								xp.left = x;
							else
								xp.right = x;
							root = balanceInsertion(root, x);
							break;
						}
					}
				}
			}
			moveRootToFront(tab, root);
		}

		/**
		 * Returns a list of non-TreeNodes replacing those linked from
		 * this node.
		 */
		final Node<K,V> untreeify(HashMap<K,V> map) {
			Node<K,V> hd = null, tl = null;
			for (Node<K,V> q = this; q != null; q = q.next) {
				Node<K,V> p = map.replacementNode(q, null);
				if (tl == null)
					hd = p;
				else
					tl.next = p;
				tl = p;
			}
			return hd;
		}

		/**
		 *
		 */
		/**
		 * putVal的树版本.
		 * @param map 当前map
		 * @param tab 当前tab
		 * @param h   当前要插入元素的hash值(已经经过抗扰动计算)
		 * @param k   当前要put的key
		 * @param v   当前要put的value
		 * @return
		 */
		final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
		                               int h, K k, V v) {
			Class<?> kc = null;
			boolean searched = false;
			// 找到整颗完整树的root节点
			TreeNode<K,V> root = (parent != null) ? root() : this;
			// 从root节点开始寻找
			for (TreeNode<K,V> p = root;;) {
				// dir标识方向(-1为左、1为右)、ph标识当前树节点的hash值、pk为当前树节点的key值
				int dir, ph; K pk;
				// 如果当前树节点的hash值大于要插入的节点的hash值
				if ((ph = p.hash) > h)
					// 标识新节点会放在当前树节点的左边
					dir = -1;
				// 如果当前树节点的hash值小于要插入的节点的hash值
				else if (ph < h)
					// 标识新节点会放在当前树节点的右边
					dir = 1;
				// 如果当前树节点的key值物理地址等于要插入的节点或者equals方法比较结果相等直接返回就算了
				else if ((pk = p.key) == k || (k != null && k.equals(pk)))
					return p;
				// 如果hash值相等、key比较又不相等, 那么好办, 如果都实现了Comparable接口则通过Comparable来比较
				else if ((kc == null &&
						(kc = comparableClassFor(k)) == null) ||
						(dir = compareComparables(kc, k, pk)) == 0) {
					// 如果比较完了还相等或者无法通过Comparable接口比较, 那么我们第一次遇到这种情况就分别从左、右子树中去找, 找到即返回
					// 为什么只有第一次遇到这种情况才从两颗子树找呢? 因为第一次找的时候就已经把所有节点都找遍了, 要是第二次再遇到那还需要找吗?
					// 肯定不需要了呀, 不用找了肯定不存在, 直接判断一下该放哪边吧
					if (!searched) {
						TreeNode<K,V> q, ch;
						searched = true;
						if (((ch = p.left) != null &&
								(q = ch.find(h, k, kc)) != null) ||
								((ch = p.right) != null &&
										(q = ch.find(h, k, kc)) != null))
							return q;
					}
					// 实在没法的话就比较原始hash值吧
					dir = tieBreakOrder(k, pk);
				}

				// 经过上面的步骤我们肯定判断出来该放在哪里了
				// 我们就新建一个节点出来, 然后插入这个节点, 插在哪里呢?
				// 如果这个节点左/右孩子节点为null, 那就插在左/右孩子节点的位置, 插入之后调整链表关系(将新插入的节点作为父节点的后继节点)
				// 如果这些节点不为null的话, 直接开启下一轮循环
				TreeNode<K,V> xp = p;
				if ((p = (dir <= 0) ? p.left : p.right) == null) {
					Node<K,V> xpn = xp.next;
					TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
					if (dir <= 0)
						xp.left = x;
					else
						xp.right = x;
					xp.next = x;
					x.parent = x.prev = xp;
					if (xpn != null)
						((TreeNode<K,V>)xpn).prev = x;
					moveRootToFront(tab, balanceInsertion(root, x));
					return null;
				}
			}
		}

		/**
		 * Removes the given node, that must be present before this call.
		 * This is messier than typical red-black deletion code because we
		 * cannot swap the contents of an interior node with a leaf
		 * successor that is pinned by "next" pointers that are accessible
		 * independently during traversal. So instead we swap the tree
		 * linkages. If the current tree appears to have too few nodes,
		 * the bin is converted back to a plain bin. (The test triggers
		 * somewhere between 2 and 6 nodes, depending on tree structure).
		 */
		final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
		                          boolean movable) {
			int n;
			if (tab == null || (n = tab.length) == 0)
				return;
			int index = (n - 1) & hash;
			TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
			TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
			if (pred == null)
				tab[index] = first = succ;
			else
				pred.next = succ;
			if (succ != null)
				succ.prev = pred;
			if (first == null)
				return;
			if (root.parent != null)
				root = root.root();
			if (root == null || root.right == null ||
					(rl = root.left) == null || rl.left == null) {
				tab[index] = first.untreeify(map);  // too small
				return;
			}
			TreeNode<K,V> p = this, pl = left, pr = right, replacement;
			if (pl != null && pr != null) {
				TreeNode<K,V> s = pr, sl;
				while ((sl = s.left) != null) // find successor
					s = sl;
				boolean c = s.red; s.red = p.red; p.red = c; // swap colors
				TreeNode<K,V> sr = s.right;
				TreeNode<K,V> pp = p.parent;
				if (s == pr) { // p was s's direct parent
					p.parent = s;
					s.right = p;
				}
				else {
					TreeNode<K,V> sp = s.parent;
					if ((p.parent = sp) != null) {
						if (s == sp.left)
							sp.left = p;
						else
							sp.right = p;
					}
					if ((s.right = pr) != null)
						pr.parent = s;
				}
				p.left = null;
				if ((p.right = sr) != null)
					sr.parent = p;
				if ((s.left = pl) != null)
					pl.parent = s;
				if ((s.parent = pp) == null)
					root = s;
				else if (p == pp.left)
					pp.left = s;
				else
					pp.right = s;
				if (sr != null)
					replacement = sr;
				else
					replacement = p;
			}
			else if (pl != null)
				replacement = pl;
			else if (pr != null)
				replacement = pr;
			else
				replacement = p;
			if (replacement != p) {
				TreeNode<K,V> pp = replacement.parent = p.parent;
				if (pp == null)
					root = replacement;
				else if (p == pp.left)
					pp.left = replacement;
				else
					pp.right = replacement;
				p.left = p.right = p.parent = null;
			}

			TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

			if (replacement == p) {  // detach
				TreeNode<K,V> pp = p.parent;
				p.parent = null;
				if (pp != null) {
					if (p == pp.left)
						pp.left = null;
					else if (p == pp.right)
						pp.right = null;
				}
			}
			if (movable)
				moveRootToFront(tab, r);
		}

		/**
		 * Splits nodes in a tree bin into lower and upper tree bins,
		 * or untreeifies if now too small. Called only from resize;
		 * see above discussion about split bits and indices.
		 *
		 * @param map the map
		 * @param tab the table for recording bin heads
		 * @param index the index of the table being split
		 * @param bit the bit of hash to split on
		 */
		final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
			TreeNode<K,V> b = this;
			// Relink into lo and hi lists, preserving order
			TreeNode<K,V> loHead = null, loTail = null;
			TreeNode<K,V> hiHead = null, hiTail = null;
			int lc = 0, hc = 0;
			for (TreeNode<K,V> e = b, next; e != null; e = next) {
				next = (TreeNode<K,V>)e.next;
				e.next = null;
				if ((e.hash & bit) == 0) {
					if ((e.prev = loTail) == null)
						loHead = e;
					else
						loTail.next = e;
					loTail = e;
					++lc;
				}
				else {
					if ((e.prev = hiTail) == null)
						hiHead = e;
					else
						hiTail.next = e;
					hiTail = e;
					++hc;
				}
			}

			if (loHead != null) {
				if (lc <= UNTREEIFY_THRESHOLD)
					tab[index] = loHead.untreeify(map);
				else {
					tab[index] = loHead;
					if (hiHead != null) // (else is already treeified)
						loHead.treeify(tab);
				}
			}
			if (hiHead != null) {
				if (hc <= UNTREEIFY_THRESHOLD)
					tab[index + bit] = hiHead.untreeify(map);
				else {
					tab[index + bit] = hiHead;
					if (loHead != null)
						hiHead.treeify(tab);
				}
			}
		}

		/* ------------------------------------------------------------ */
		// Red-black tree methods, all adapted from CLR

		static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
		                                      TreeNode<K,V> p) {
			TreeNode<K,V> r, pp, rl;
			if (p != null && (r = p.right) != null) {
				if ((rl = p.right = r.left) != null)
					rl.parent = p;
				if ((pp = r.parent = p.parent) == null)
					(root = r).red = false;
				else if (pp.left == p)
					pp.left = r;
				else
					pp.right = r;
				r.left = p;
				p.parent = r;
			}
			return root;
		}

		static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
		                                       TreeNode<K,V> p) {
			TreeNode<K,V> l, pp, lr;
			if (p != null && (l = p.left) != null) {
				if ((lr = p.left = l.right) != null)
					lr.parent = p;
				if ((pp = l.parent = p.parent) == null)
					(root = l).red = false;
				else if (pp.right == p)
					pp.right = l;
				else
					pp.left = l;
				l.right = p;
				p.parent = l;
			}
			return root;
		}

		/**
		 * 返回进行平衡之后的根节点
		 * @param root 原本的根节点
		 * @param x 新插入的节点
		 * @return
		 */
		static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
		                                            TreeNode<K,V> x) {
			// 进行平衡的时候, 首先我们要默认插入的节点一定是红色的
			x.red = true;
			// xp即x parent父节点, xxp即祖父节点, xxpl叔叔节点, xppr伯伯节点
			for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
				// 如果是根节点, 那么必须是黑色
				if ((xp = x.parent) == null) {
					x.red = false;
					return x;
				}
				// 父节点是黑的(都是黑的了, 自己刚插入进来也没有子节点, 那就是说不可能有黑色的后代, 直接不用比了),
				// 或者没有祖父节点(没有祖父节点, 那只能说明父节点就是根节点, 那还调整个屁, 也不用调整了)
				else if (!xp.red || (xpp = xp.parent) == null)
					return root;
				// 如果叔叔节点等于父节点, 意思就是父节点其实是祖父节点的左子树
				if (xp == (xppl = xpp.left)) {
					// 如果有伯伯, 而且伯伯是红的
					// 此时父节点是红的, 伯伯是红的, 那祖父肯定是黑的, 那直接把祖父改成红的, 祖父的两个儿子改成黑的
					// 然后因为祖父变红了, 又要去看一下祖父的父节点、叔节点、祖父节点等, 就循环了
					if ((xppr = xpp.right) != null && xppr.red) {
						xppr.red = false;
						xp.red = false;
						xpp.red = true;
						x = xpp;
					}
					// 如果没有伯伯, 或者伯伯是黑的
					else {
						// 如果我们插入的节点是往往右子树上面插入的
						if (x == xp.right) {
							root = rotateLeft(root, x = xp);
							xpp = (xp = x.parent) == null ? null : xp.parent;
						}
						if (xp != null) {
							xp.red = false;
							if (xpp != null) {
								xpp.red = true;
								root = rotateRight(root, xpp);
							}
						}
					}
				}
				else {
					if (xppl != null && xppl.red) {
						xppl.red = false;
						xp.red = false;
						xpp.red = true;
						x = xpp;
					}
					else {
						if (x == xp.left) {
							root = rotateRight(root, x = xp);
							xpp = (xp = x.parent) == null ? null : xp.parent;
						}
						if (xp != null) {
							xp.red = false;
							if (xpp != null) {
								xpp.red = true;
								root = rotateLeft(root, xpp);
							}
						}
					}
				}
			}
		}

		static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
		                                           TreeNode<K,V> x) {
			for (TreeNode<K,V> xp, xpl, xpr;;)  {
				if (x == null || x == root)
					return root;
				else if ((xp = x.parent) == null) {
					x.red = false;
					return x;
				}
				else if (x.red) {
					x.red = false;
					return root;
				}
				else if ((xpl = xp.left) == x) {
					if ((xpr = xp.right) != null && xpr.red) {
						xpr.red = false;
						xp.red = true;
						root = rotateLeft(root, xp);
						xpr = (xp = x.parent) == null ? null : xp.right;
					}
					if (xpr == null)
						x = xp;
					else {
						TreeNode<K,V> sl = xpr.left, sr = xpr.right;
						if ((sr == null || !sr.red) &&
								(sl == null || !sl.red)) {
							xpr.red = true;
							x = xp;
						}
						else {
							if (sr == null || !sr.red) {
								if (sl != null)
									sl.red = false;
								xpr.red = true;
								root = rotateRight(root, xpr);
								xpr = (xp = x.parent) == null ?
										null : xp.right;
							}
							if (xpr != null) {
								xpr.red = (xp == null) ? false : xp.red;
								if ((sr = xpr.right) != null)
									sr.red = false;
							}
							if (xp != null) {
								xp.red = false;
								root = rotateLeft(root, xp);
							}
							x = root;
						}
					}
				}
				else { // symmetric
					if (xpl != null && xpl.red) {
						xpl.red = false;
						xp.red = true;
						root = rotateRight(root, xp);
						xpl = (xp = x.parent) == null ? null : xp.left;
					}
					if (xpl == null)
						x = xp;
					else {
						TreeNode<K,V> sl = xpl.left, sr = xpl.right;
						if ((sl == null || !sl.red) &&
								(sr == null || !sr.red)) {
							xpl.red = true;
							x = xp;
						}
						else {
							if (sl == null || !sl.red) {
								if (sr != null)
									sr.red = false;
								xpl.red = true;
								root = rotateLeft(root, xpl);
								xpl = (xp = x.parent) == null ?
										null : xp.left;
							}
							if (xpl != null) {
								xpl.red = (xp == null) ? false : xp.red;
								if ((sl = xpl.left) != null)
									sl.red = false;
							}
							if (xp != null) {
								xp.red = false;
								root = rotateRight(root, xp);
							}
							x = root;
						}
					}
				}
			}
		}

		/**
		 * 递归invariant(不变)检查
		 * 其实就是检查对象是否满足红黑树和双链表的特性, 因为并发情况下可能发生异常
		 * @param t 一颗树的根节点
		 * @return
		 */
		static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
			TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
					tb = t.prev, tn = (TreeNode<K,V>)t.next;
			// 某一个节点的前驱节点的后继节点不是他自己, 那么说明不满足双链表特性, 返回false
			if (tb != null && tb.next != t)
				return false;
			// 某一个节点的后继节点的前驱节点不是他自己, 那么说明不满足双链表特性, 返回false
			if (tn != null && tn.prev != t)
				return false;
			// 如果某一个节点既不是其父节点的左孩子也不是右孩子, 那这棵树就有问题, 返回false
			if (tp != null && t != tp.left && t != tp.right)
				return false;
			// 如果左孩子的父节点不是他自己 or 左孩子的值比他自己的值要大, 返回fasle
			if (tl != null && (tl.parent != t || tl.hash > t.hash))
				return false;
			// 如果右孩子的父节点不是他自己 or 右孩子的值比他自己的值要小, 返回false
			if (tr != null && (tr.parent != t || tr.hash < t.hash))
				return false;
			// 如果他是红的, 左孩子、右孩子都是红的, 返回false
			if (t.red && tl != null && tl.red && tr != null && tr.red)
				return false;
			// 分别检查左、又子树
			if (tl != null && !checkInvariants(tl))
				return false;
			if (tr != null && !checkInvariants(tr))
				return false;
			return true;
		}
	}

}
